Универсальный подход к параллельному планированию для буферного анализа векторных данных полилиний и полигонов на традиционных ГИС-платформах

1 | ВВЕДЕНИЕ

Буфер в ГИС определяется как зона вокруг геометрического географического объекта, измеряемая в единицах расстояния или времени (Ramasubramanian, 2009). Буферный анализ играет важную роль во многих приложениях ГИС, таких как экологический мониторинг и управление (Saha, Gupta, Sarkar, Arora, & Csaplovics, 2005; Silva & Williams, 2001), здоровье человека (English et al., 1999; Vine, Degnan, & Hanchette, 1997), ландшафтное и городское планирование (Mhuireach et al., 2016; Xiang, 1996), обработка и представление географических данных (Liu, Xiong, Hu, & Shan, 2015; Tveite & Langaase, 1999) и анализ зданий (Bei, Guo, & Huang, 2019; Guo, Liu, Xu, & Huang, 2020).

Алгоритмы буферного анализа для двумерных векторных данных, как правило, делятся на два типа: основанные на векторных и растровых данных. Хотя стабильность и точность генерации буферов для векторных данных значительно улучшились за последние десятилетия, эти алгоритмы по-прежнему требуют значительного времени вычислений при работе с большими объёмами данных из-за их высокой вычислительной сложности.

Несмотря на предложенные методы использования векторных и растровых алгоритмов, они не могли удовлетворить требованиям быстрой обработки растущих объёмов пространственных данных. Поэтому многие исследователи сосредоточили усилия на параллельных вычислениях (Simion, Ray, & Brown, 2012).

Willebeek-LeMair и Reeves (1988a, 1988b) предложили методы параллельного выращивания областей для изображений, содержащих большое количество регионов, на SIMD и MIMD параллельных системах. С помощью таких технологий параллельных вычислений, как кластеры серверов (Hawick, Coddington, & James, 2003), многоядерные CPU (Gao, Wang, Li, & Shen, 2005; Li, Jiang, Yang, Huang, & Rice, 2013; Yang, Wong, Yang, Kafatos, & Li, 2005) или GPU (Guo, Huang, Guan, Xie, & Wu, 2017; Tang, 2013; Xia, Kuang, & Li, 2011; Zhao, Padmanabhan, & Wang, 2013), грид-вычисления (Wang & Armstrong, 2003) и облачные вычисления (Yang et al., 2011; Yang, Xu, & Nebert, 2013), можно оптимизировать процедуры извлечения и обработки данных для задач пространственных вычислений. Основной принцип этих параллельных технологий заключается в разделении вычислительно ёмких задач на несколько подзадач и их параллельном распределении по нескольким вычислительным единицам. Для достижения максимального ускорения балансировка нагрузки является одной из ключевых проблем, требующих решения (Guo, Huang, & Xie, 2015).

Некоторые исследователи переработали существующие алгоритмы буферного анализа, чтобы максимально использовать возможности параллельных вычислительных фреймворков для достижения лучшей параллельной производительности и повышения эффективности алгоритмов. Guan, Wu и Li (2012) предложили парадигму разделения-слияния для обработки пространственных данных и представили устойчивый параллельный фреймворк в кластерной среде для её поддержки. Некоторые исследователи предложили параллельный алгоритм буферного анализа на основе объединения областей и MPI (Message Passing Interface) для повышения производительности буферного анализа при обработке больших наборов данных (Fan, Ji, Gu, & Sun, 2014). Fan также представил параллельный алгоритм анализа пересечения векторных полигонов на основе растрирования с использованием OpenMP и MPI, расширенный алгоритмом отсечения полигонов на основе растрирования (Fan et al., 2018). Ma, Wu, Chen, Li и Jing (2019) предложили ориентированный на визуализацию метод анализа буферного наложения на основе полностью оптимизированной гибридной параллельной архитектуры обработки. Они представили эффективный метод генерации буферов на основе пространственного индекса и эффективный метод оптимизации наложения на основе преобразования множеств для получения результатов.

Некоторые исследователи разработали распределённый пространственный индекс на основе Apache Storm, который является открытой распределённой системой вычислений в реальном времени (Zhang et al., 2016). Du et al. (2017) предложили эффективный высокопроизводительный многопоточный алгоритм, в котором Spark решает проблема узких мест, преобразуя ранее неэффективное каскадное попарное пространственное соединение в высокопроизводительный подход. Yao et al. (2017) представили подход на основе пространственного кодирования для разделения больших пространственных данных в Hadoop. Было достигнуто значительное улучшение качество пространственных индексов, перекоса данных в HDFS и производительности пространственных запросов. Shen, Chen, Wu и Jing (2018) предложили ориентированный на кластерные вычисления параллельный алгоритм генерации векторных буферов, который включает метод разделения данных на основе кривой Гильберта, стратегию обработки перекоса данных и объектов, пересекающих границы, а также глубокий древовидный метод слияния.

Упомянутые выше параллельные подходы позволили достичь высокой производительности пространственных операций. Большинство существующих алгоритмов, основанных на стратегии параллелизма, ориентированной на алгоритм, были улучшены для соответствия соответствующему параллельному фреймворку или конкретным требованиям (например, визуализации, быстрого онлайн-отображения и т.д.). Хотя эти алгоритмы демонстрируют высокую производительность, улучшение каждого существующего алгоритма является очень сложным, требующим значительной переработки и повторной разработки. Следовательно, традиционные ГИС-платформы (например, QGIS, ArcGIS, MapGIS и др.) не могут удовлетворить требованиям быстрой обработки больших пространственных данных с использованием этих параллельных стратегий. Алгоритмы, использующие стратегии параллелизма, ориентированные на данные, в основном реализованы в параллельных фреймворках Hadoop, Spark или их расширениях. Использование возможностей параллельных вычислений этих фреймворков является очень эффективным способом ускорения пространственного анализа больших данных. Однако пространственные данные необходимо конвертировать в другой формат, чтобы их можно было хранить в этих параллельных фреймворках. Конвертация данных — очень трудоёмкий процесс. Чем больше объём пространственных данных, тем дольше время конвертации формата. Было бы сложно конвертировать огромные наборы векторных данных из традиционных ГИС-платформ в эти новые распределённые базы данных. Кроме того, традиционные ГИС-платформы не используют стратегии параллелизма, ориентированные на данные, для решения проблемы быстрой обработки больших пространственных данных. Изменить текущий формат пространственных данных ГИС-платформ сложно, особенно когда объём данных очень велик. В итоге, разработка рационального и применимого параллельного подхода, использующего алгоритмы пространственного анализа и формат данных традиционных ГИС-платформ, остаётся сложной задачей.

В среде параллельных вычислений достижение балансировки нагрузки является ключевым моментом для повышения производительности обработки векторных данных. Стратегия пространственной декомпозиции области, которая делит область набора данных на неравномерные подобласти так, чтобы вычислительная интенсивность равномерно распределялась по подобластям, является применимой стратегией и широко используется некоторыми исследователями. Она применялась в параллельной пространственной интерполяции (Wang & Armstrong, 2003), параллельной обработке растровых данных (Guan & Clarke, 2010) и параллельной визуализации векторных данных (Guo, Guan, et al., 2015). Однако разбить пространственную область данных на желаемое количество подобластей сложно. Guo, Guan, et al. (2015) предложили метод декомпозиции на основе вычислительной интенсивности (CID), использовав непрерывную незапутанную пространственно-заполняющую кривую и список вычислительной интенсивности для равномерного разделения пространственных областей. Однако CID применим только для визуализации векторных данных. Если некоторые объекты отображаются в двух подобластях, отображаемый результат всё равно будет корректным. Этот метод не удовлетворяет требованию, чтобы объекты, частично находящиеся в подобласти, правильно делились на параллельные задачи и буферная зона одного объекта генерировалась только один раз в каждой параллельной задаче.

В данной статье представлен универсальный подход к параллельному планированию для генерации векторных буферов на традиционных ГИС-платформах. Без переразработки инструментов генерации буферов программного обеспечения ГИС-платформы или конвертации форматов данных предлагаемый подход направлен на значительное повышение вычислительной производительности за счёт использования архитектуры параллельных вычислений. Сначала определяются ключевые факторы вычислительной интенсивности генерации буферов для векторных объектов (т.е. полилиний и полигонов). Затем строится сетка вычислительной интенсивности (CIG), где каждая ячейка представляет вычислительную интенсивность в своём местоположении. Предлагается двухэтапный механизм балансировки нагрузки. Во-первых, вся область набора пространственных векторных данных делится на подобласти с максимально равной вычислительной интенсивностью каждой подобласти задачи. Во-вторых, на основе вычислительной интенсивности объектов и подобластей, сгенерированных на первом этапе декомпозиции, объекты равномерно распределяются внутри подобластей по задачам параллельного буферного анализа для балансировки нагрузки.

Оставшаяся часть статьи организована следующим образом. В разделе 2 описывается процесс оценки вычислительной интенсивности и подход к декомпозиции. В разделе 3 представлена серия экспериментов для демонстрации эффективности и производительности нового подхода. Раздел 4 содержит выводы и предложения для будущей работы.

2 | МЕТОДЫ

2.1 | Ключевые факторы вычислительной интенсивности

Генерация буфера для векторных объектов — это вычислительно ёмкий процесс, требующий значительных вычислительных ресурсов и времени для больших наборов векторных данных. Балансировка нагрузки — одна из ключевых проблем, которые необходимо решить в параллельной среде. Для разделения вычислительных областей на параллельные задачи с балансировкой нагрузки необходимо точно оценить вычислительную интенсивность каждого объекта. Поэтому исследуются внутренние операции буферного анализа для поиска ключевых влияющих факторов. В алгоритме генерации буфера есть три основных шага. Сначала необходимо получить геометрию объекта. Во-вторых, вычисляется буферная зона. В-третьих, буферная зона записывается в файл пространственных данных или пространственную базу данных. В данном исследовании в качестве показателя вычислительной интенсивности для буферного анализа используется время вычислений. Поскольку каждая вершина объекта должна быть обработана на всех этапах генерации буфера, очевидно, что важнейшим фактором времени вычислений является количество вершин каждого объекта. Следовательно, проводится ряд тестов с использованием группы реальных наборов данных для демонстрации взаимосвязи между фактором и временем вычислений. Как показано на Рисунке 1, набор данных A содержит 200 полигональных объектов с количеством вершин от 58 до 9 985; общее количество вершин составляет 999 690. Набор данных B — это набор данных полилиний с таким же количеством вершин и объектов, как и в наборе данных A.

В тестами количество вершин полигональных и полилинейных объектов в реальных наборах данных различается. С использованием MapGIS SDK тестируется время вычислений для каждого объекта полилинии и полигона в наборе данных для трёх шагов буферного анализа, как показано в Таблице 1. Корреляции между факторами и временем вычислений для трёх шагов являются значимыми (коэффициент корреляции > 0,965; значимость = 0 [корреляция Пирсона]). Это указывает на то, что предварительно выбранный кандидат-фактор подходит для представления вычислительной интенсивности буферного анализа полилиний и полигонов. Как показано на Рисунке 2, существует стабильная линейная зависимость между временем вычислений и количеством вершин объекта. Поэтому для эффективного соответствия этой линейной зависимости выбирается линейная модель. Значения R² соответствующих линейных моделей зависимостей показаны в Таблице 2. Значимость этих линейных моделей равна 0.

Чтобы обеспечить универсальность исследований, те же тесты проводятся с использованием ArcGIS и QGIS. Получены аналогичные линейные зависимости между временем вычислений и количеством вершин. Таким образом, вычислительная интенсивность (время вычислений) генерации буфера для объекта полигона или полилинии может быть представлена как:

где x — количество вершин объекта полилинии или полигона; f₁(x), f₂(x), f₃(x) — линейные функции от x. f₁(x), f₂(x), f₃(x) выражают время вычислений трёх шагов буферного анализа соответственно: получение геометрии из набора данных; генерация результатов буфера; запись результатов в файл или базу данных.

Вычислительная интенсивность создания буфера для группы полилиний или полигонов может быть тогда выражена следующим образом:

где n — количество объектов, а x_i — количество вершин объекта i.

Рисунок 1 — Группа реальных наборов данных для тестирования взаимосвязи между фактором и временем вычислений
(a) Набор данных A
(b) Набор данных B

После определения ключевого фактора для вычислительной интенсивности буферного анализа, функции преобразования вычислительной интенсивности (CITF) могут быть использованы для представления математической взаимосвязи между фактором и вычислительной интенсивностью. Следовательно, вычислительная интенсивность генерации результатов буферного анализа для группы полигональных и полилинейных объектов может быть оценена.

2.2 Построение CITF

Как показано в Таблице 2, эти линейные модели могут быть использованы для генерации CITF. Сначала могут быть построены суб-CITF для одиночного объекта полигона или полилинии, как показано в уравнениях (3) и (4):

где CL, CP — это соответственно время вычислений для буферного анализа полилинии и полигона. x — количество вершин объекта полилинии или полигона; a₁, a₂, a₃, a₄, a₅, a₆ — это соответственно угловые коэффициенты линейных функций трёх шагов, а b₁, b₂, b₃, b₄, b₅, b₆ — соответственно точки пересечения.

Рисунок 2 — Время вычислений для полилиний и полигонов на трёх шагах буферного анализа: (a) шаг получения для полилинии; (b) шаг буфера для полилинии; (c) шаг записи для полилинии; (г) шаг получения для полигона; (д) шаг буфера для полигона; и (е) шаг записи для полигона

Затем могут быть построены общие CITF для набора полилиний и полигонов, которые представляют вычислительную интенсивность группы полилиний или полигонов:

где WL — общее время вычислений для группы полилиний, а WP — общее время вычислений для группа полигонов; n — количество полилиний или полигонов; а x_i — количество вершин объекта полилинии или полигона i.

CITF обеспечивают эффективную оценку вычислительной интенсивности генерации буферов для группы полилиний или полигонов. Это важно для пространственного представления вычислительной интенсивности буферного анализа, рассматриваемого в следующем разделе. Коэффициенты (т.е. a₁ - a₆, b₁ - b₆) CITF для разного ГИС-программного обеспечения (т.е. QGIS, ArcGIS, MapGIS и т.д.) различны, но линейные зависимости между временем вычислений и количеством вершин сохраняются. Статистические методы универсальны для определения взаимосвязи между временем вычислений и количеством вершин объекта и могут быть легко получены при различных алгоритмах, аппаратном обеспечении, программном обеспечении и операционных системах. Следовательно, перед построением пространственного представления вычислительной интенсивности буферного анализа для конкретного ГИС-программного обеспечения коэффициенты должны быть откалиброваны с помощью набора тестов и статистических анализов (см. раздел 3.1).

2.3 | Пространственное представление вычислительной интенсивности

Чтобы обеспечить эффективность универсального метода параллельного планирования, должно быть правильно описано пространственное представление вычислительной интенсивности генерации буфера. В данном исследовании расширен подход поверхности вычислительной интенсивности (CIS), предложенный Wang и Armstrong (2009). На основе CIS пространственная вычислительная область может быть разделена на несколько подобластей, которые будут обрабатываться на каждой параллельной вычислительной единице. Для построения CIS используется CIG. Пространственная вычислительная область векторного слоя делится на группу регулярных ячеек одинаковой формы и размеров, так что может быть сгенерирована CIG для буферного анализа. CIG размером 4 × 4 для набора данных полигонов показана на Рисунке 3, где W_ij — это вычислительная интенсивность ячейки в строке i и столбце j сетки. W_ij может быть рассчитана с помощью уравнения (5) или (6) соответственно для полилиний или полигонов.

При расчёте W_ij для ячейки вычислительная интенсивность объектов должна быть полностью добавлена к общей вычислительной интенсивности, если они расположены полностью внутри ячейки. Но для объектов, которые частично находятся внутри ячейки, нецелесообразно повторно вычислять вычислительную интенсивность в двух или более ячейках (Guo, Guan, et al., 2015), поскольку это снизит точность пространственного представления вычислительной интенсивности. Если используется метод полного вычисления вычислительной интенсивности ячейки (CCCLI), вычислительная интенсивность объектов, частично находящихся внутри ячейки, будет повторно вычисляться для более чем двух ячеек. Это приведёт к завышенному значению W_ij для ячейки. Чтобы решить эту проблему, в данном исследовании вычислительная интенсивность каждого объекта, частично находящегося внутри ячейки, вычисляется на основе доли вершин объекта, расположенных в ячейке. Это называется частичным вычислением вычислительной интенсивности ячейки (PCCIL) в данном исследовании. Как показано на Рисунке 4, есть четыре объекта полилинии, расположенные в ячейке в строке 0 и столбце 0 сетки. Количество вершин объекта C, который полностью находится внутри ячейки, равно 4, а доля вершин в ячейке для объектов A, B и D составляет соответственно 1/2, 1/4 и 1/2. Таким образом, W₀₀ может быть вычислена из уравнения (7), где CL_A, CL_B, CL_C, и CL_D — это соответственно вычислительная интенсивность объектов A, B, C и D:

Рисунок 3 — CIG 4 × 4 для векторных данных полигонов

Рисунок 4 — Объекты, полностью или частично расположенные в ячейке

2.4 | Двухэтапная адаптивная пространственная декомпозиция для параллельного буферного анализа

Идеальная декомпозиция для параллельного буферного анализа должна обеспечивать, чтобы каждая задача имела схожую вычислительную интенсивность, чтобы все параллельные задачи могли быть завершены одновременно. С помощью анализа буфера вычислительная интенсивность каждого отдельного объекта может быть получена через CITF, и объекты могут быть напрямую разделены на несколько параллельных потоков для проведения буферного анализа в соответствии с вычислительной интенсивностью. Но этот метод требует извлечения всех объектов по одному, что будет чрезвычайно затратно по времени, особенно если векторных данных много. Поэтому в данной статье предлагается двухэтапный метод адаптивной пространственной декомпозиции (TASD) для параллельного буферного анализа. Целью адаптивной пространственной декомпозиции первого этапа (FASD) было сделать сумму вычислительной интенсивности для подобласти каждой задачи максимально равной. На втором этапе адаптивной пространственной декомпозиции (SASD) на основе вычислительной интенсивности объектов объекты, частично находящиеся внутри подобласти, сгенерированной на первом этапе декомпозиции, равномерно распределяются по смежным задачам подобластей.

2.4.1 Адаптивная пространственная декомпозиция первого этапа

Согласно стратегии пространственной декомпозиции области набора данных, связанные исследования можно классифицировать на две категории: регулярная декомпозиция и адаптивная пространственная декомпозиция. Стратегия регулярной декомпозиции уделяет внимание только равномерному разделению подобластей по площади. Метод вертикальной декомпозиции (VD) делит всю область на одинаковые по размеру столбцеобразные подобласти (Рисунок 5а), в то время как горизонтальная декомпозиция (HD) генерирует одинаковые по размеру строчеобразные подобласти (Рисунок 5b). Вертикально-горизонтальная декомпозиция (VHD) формирует блокообразные подобласти как по столбцам, так и по строкам (Рисунок 5c). Но эти методы регулярной декомпозиции не учитывают пространственное распределение объектов в наборе данных и просто делят область набора данных на подобласти равными по площади. Если объекты сильно сгруппированы, а не равномерно распределены в пространстве, методы регулярной декомпозиции могут привести к значительному дисбалансу нагрузки между параллельными задачами. Поэтому для решения этой проблемы представлена стратегия адаптивной пространственной декомпозиции на основе вычислительной интенсивности.

Вторая категория — это стратегия пространственной адаптивной декомпозиции, которая делит область набора данных на неравномерные по размеру подобласти так, чтобы вычислительная интенсивность равномерно распределялась по подобластям. Некоторые исследователи используют подходы адаптивной пространственной декомпозиции в параллельной пространственной интерполяции (Wang & Armstrong, 2003), параллельной обработке растровых данных (Guan & Clarke, 2010) и параллельной визуализации векторных данных (Guo, Guan, et al., 2015). Wang и Armstrong (2003) и Guan и Clarke (2010) использовали метод пространственной декомпозиции на основе квадродерева (QTB) (Рисунок 6а), который итеративно разделяет родительскую область на четыре одинаковые дочерние области до тех пор, пока рабочая нагрузка не распределится равномерно по результирующим подобластям. Однако разбить область пространственных данных на желаемое количество подобластей сложно, потому что QTB-декомпозиция генерирует число подобластей, увеличивающееся на 3 каждый раз при итеративном разделении родительской области. Guo, Guan, et al. (2015) предложили метод CID (Рисунок 6b), использовав непрерывную незапутанную пространственно-заполняющую кривую и список вычислительной интенсивности для равномерного разделения желаемого числа подобластей. Однако CID не удовлетворяет требованию, чтобы объекты, частично находящиеся в подобласти, правильно делились на параллельную задачу и буферная зона одного объекта генерировалась только один раз в каждой параллельной задаче. На Рисунке 6а объект A присутствует и в подобласти 1, и в подобласти 3. В этом случае сложно принять решение о назначении объекта A в подобласть 1 или 3, а затем распределить объекты в подобласти по параллельной задаче для буферного анализа. Таким образом, метод пространственной декомпозиции QTB имеет тот же недостаток при распределении объектов, частично находящихся в подобласти. Как показано на Рисунке 6b, объект A пересекает подобласти 2, 3 и 4. Разработка стратегии для назначения объекта A в подобласть 2, 3 или 4 является сложной и затратной по времени и серьёзно снизит производительность и эффективность параллельного буферного анализа.

Рисунок 5 — Три метода регулярной декомпозиции: (a) вертикальная декомпозиция; (b) горизонтальная декомпозиция; и (c) вертикально-горизонтальная декомпозиция

Рисунок 6 — Три метода пространственной адаптивной декомпозиции: (a) декомпозиция на основе квадродерева; (b) декомпозиция на основе вычислительной интенсивности; и (c) адаптивная пространственная декомпозиция первого этапа

Рисунок 7 — Рабочий процесс адаптивной пространственной декомпозиции первого этапа (N = 4)

Ни один из вышеупомянутых методов не может удовлетворить потребности декомпозиции задач параллельного буферного анализа, поэтому для решения проблемы предлагается метод TASD. Метод FASD основан на методах HD или VD для пространственной адаптивной декомпозиции. Вычислительная интенсивность пересекающегося объекта рассчитывается только для одной подобласти, и метод VHD не используется, поскольку ему сложно решить проблему разделения объектов, частично находящихся в двух или более подобластях. В данной статье для FASD на основе сеток вычислительной интенсивности используется метод HD (Рисунок 6c). Этот этап может эффективно разделить область набора данных на подобласти со схожей вычислительной интенсивностью. Затем на этапе SASD используется стратегия назначения объектов, частично находящихся в двух подобластях, в параллельную задачу, как показано на Рисунке 7. После формирования CIG сначала вычисляется сумма (W₀, W₁, W₂, W₃) вычислительной интенсивности ячеек для каждой строки. Затем получается W_total — общая сумма вычислительной интенсивности всех ячеек, и W_task (вычислительная интенсивность подзадачи) получается делением W_total на N (количество задач). Впоследствии сумма вычислительной интенсивности каждой строки сравнивается с W_task. Если сумма вычислительной интенсивности строки больше W_task, вычисляется соответствующая доля области строки так, чтобы вычислительная интенсивность области была равна W_task, и тогда эта область формирует подобласть, а оставшаяся часть области строки сравнивается с W_task как вычислительная интенсивность следующей подобласти. Если нет, вычислительная интенсивность следующей строки добавляется к вычислительной интенсивности текущей строки и затем сравнивается с W_task до тех пор, пока сумма не станет равна W_task. Таким образом, все строки будут пройдены, и все подобласти будут сгенерированы с приблизительно равной вычислительной интенсивностью.

Согласно предложенным здесь методам формирования CIG с использованием PCCIL и FASD, можно гарантировать, что все подобласти будут иметь приблизительно равную вычислительную интенсивность. Однако есть некоторые объекты, частично находящиеся в двух подобластях, что приводит к дисбалансу нагрузки между параллельными задачами, декомпозированными на первом этапе. Следовательно, должна быть разработана стратегия назначения объектов, частично находящихся в двух подобластях, в параллельную задачу, чтобы достичь баланса нагрузки между подобластями.

2.4.2 | Адаптивная пространственная декомпозиция второго этапа

После декомпозиции первого этапа баланс нагрузки между подобластями окончательно не достигнут, и ключевым является вопрос, как распределить объекты, частично находящиеся в двух подобластях. В процессе генерации CIG вычислительная интенсивность ячейки вычисляется на основе доли вершин объектов в ячейке. Следовательно, объекты, частично находящиеся в двух подобластях, разделяются пропорционально доле их вычислительной интенсивности, чтобы сбалансировать нагрузку между параллельными подзадачами. Другими словами, цель SASD — равномерно распределить объекты, частично находящиеся в двух подобластях, по каждой подобласти.

Как показано на Рисунке 8, сначала извлекаются объекты, которые частично находятся в двух подобластях, а затем вычисляется вычислительная интенсивность каждого объекта с помощью уравнения (3) [см. уравнение (8)]. Согласно доле количества вершин объекта в подобласти 2 к общему количеству вершин в подобласти 2 может быть получена частичная вычислительная интенсивность объекта в подобласти 2 [см. уравнение (9)], а также сумма частичной вычислительной интенсивности в подобласти 2 для всех объектов, частично находящихся в подобласти 2 [см. уравнение (10)]:

где W_A, W_B, W_C, и W_D — это соответственно вычислительные интенсивности объектов A, B, C и D. 5, 4, 4 и 4 — это соответственно количество вершин объектов A, B, C и D. W_A2, W_B2, W_C2, и W_D2 — это соответственно частичные вычислительные интенсивности объектов A, B, C и D в подобласти 2. 4/5, 3/4, 3/4, и 1/4 — это соответственно доли количества вершин объектов A, B, C и D в подобласти 2 от общего количества вершин в подобласти 2. W_S2 — это сумма частичной вычислительной интенсивности в подобласти 2 для всех объектов, пересекающих подобласти 2 и 3.

Затем сравнивается W_A с W_S2. Если W_A ≤ W_S2, вычислительная интенсивность следующего объекта добавляется к W_A, сумма используется для такого же сравнения до тех пор, пока сумма не станет больше W_S2, затем связанные объекты делятся на параллельную задачу 2, а оставшиеся объекты, частично находящиеся в двух подобластях, делятся на параллельную задачу 3. Если W_A > W_S2, объекты A, B и C делятся на параллельную задачу 2, а объект D — на параллельную задачу 3. Используя ту же стратегию, другие объекты, частично находящиеся в двух подобластях, делятся на две параллельные задачи. В итоге проблема балансировки нагрузки между всеми параллельными задачами решается.

Как показано на Рисунке 9, объект A пересекает более двух подобластей, и его сложно назначить в подобласть. Чтобы решить эту проблему, создаётся глобальный массив для хранения идентификаторов тех объектов, которые пересекают смежные подобласти. Перед назначением объекта, пересекающего несколько подобластей, в параллельную задачу, идентификатор объекта запрашивается в глобальном массиве. Если идентификатор объекта отсутствует в глобальном массиве, объект будет назначен, и его идентификатор будет сохранён в глобальном массиве. Если идентификатор объекта существует в глобальном массиве, объект не назначается. С помощью этого метода большие объекты, пересекающие несколько подобластей, могут быть эффективно распределены.

Рисунок 8 — Алгоритм адаптивной пространственной декомпозиции второго этапа

Рисунок 9 — Большой объект, пересекающий несколько подобластей

На практике вычислительная интенсивность генерации буфера не позволяет равномерно распределить объекты, частично находящиеся в двух подобластях, по двум параллельным задачам. Поскольку объект является географической сущностью, нецелесообразно разделять объект на несколько частей и распределять их по подпараллельным задачам для балансировки нагрузки. Буферный анализ является вычислительно ёмким и крайне затратным по времени, и разделение объектов и объединение нескольких буферных зон частей объекта в одну зону усугубит эту проблему. Поэтому предлагаемый здесь метод SASD является целесообразным решением, обеспечивающим, чтобы каждый объект полностью назначался в единую подпараллельную задачу один раз, и, таким образом, баланс нагрузки может быть достигнут насколько это возможно.

2.5 Параллельный фреймворк векторного буферного анализа для традиционных ГИС-платформ

Для универсальности и применимости вышеописанных методов для различных традиционных ГИС-платформ был разработан универсальный параллельный фреймворк векторного буферного анализа для среды параллельных вычислений (Рисунок 10). Любая традиционная ГИС-платформа может быть выбрана для проведения алгоритма параллельного буферного анализа в этом параллельном фреймворке с использованием существующего прикладного программного интерфейса (API) для буферного анализа в SDK и текущего формата данных ГИС-платформы. Векторная база данных хранит объекты полилиний и полигонов, которые будут использоваться для генерации результатов буфера. Кроме того, в этом фреймворке создаётся ещё одна база данных для хранения CIG для слоя полилиний или полигонов.

Как упоминалось в разделе 2.2, коэффициенты линейных моделей, соответствующих зависимостям между временем вычислений и количеством вершин, должны быть откалиброваны для конкретных аппаратных и программных конфигураций, чтобы вычислительная интенсивность генерации буфера для каждого векторного объекта могла быть правильно оценена, и могли быть получены CIG для представления пространственного распределения вычислительной интенсивности. Согласно PCCIL, строятся CIG различной гранулярности, которые затем сохраняются в базе данных CIG. Затем из базы данных CIG извлекается CIG определённой гранулярности для выполнения метода FASD, описанного в разделе 2.4.1, для генерации областей параллельных задач. Затем области, сгенерированные FASD, передаются на узлы параллельных вычислений. На каждом узле векторные данные запрашиваются и извлекаются из векторной базы данных с использованием области для SASD, упомянутой в разделе 2.4.2. После проведения SASD объекты, пересекающие две подобласти, равномерно распределяются по подобластям, чтобы можно было достичь баланса нагрузки между параллельными задачами. При использовании соответствующего API для генерации результатов буфера тип результата слияния (dissolving) является опциональным. Если выбран вариант слияния всех объектов, результаты буфера всех потоков уже слиты. Затем проводятся финальные операции слияния для объединения всех слитых результатов, и все результаты буфера объединяются в один. Чтобы объединить те объекты, которые пересекают смежные подобласти, сначала необходимо извлечь эти объекты, затем извлечь другие объекты, пересекающиеся с ними, и все их объединить, чтобы сгенерировать окончательный результат буфера.

Рисунок 10 — Параллельный фреймворк векторного буферного анализа для традиционных ГИС-платформ

3 | ЭКСПЕРИМЕНТЫ И АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ

Чтобы продемонстрировать применимость и масштабируемость предложенных методов и оценить производительность, была проведена серия экспериментов в рамках параллельного фреймворка буферного анализа на трёх традиционных ГИС-платформах. Во-первых, была определена оптимальная гранулярность сетки для формата данных и алгоритмов буферного анализа QGIS. Используя оптимальную гранулярность сетки, TASD сравнивался с методами регулярной декомпозиции и методами пространственной адаптивной декомпозиции. Более того, чтобы дополнительно исследовать универсальность предложенных методов, группа экспериментов также была проведена с использованием платформ ArcGIS и MapGIS. Вычислительные узлы экспериментов состояли из двух 8-ядерных процессоров Intel Xeon E5620 с частотой 2,4 ГГц и 16 ГБ оперативной памяти. Эксперименты проводились соответственно с использованием QGIS 3.4.8, ArcGIS 10.2.1 и MapGIS 10.3.3.1 SDK.

3.1 | Коэффициенты CITF для QGIS

Был проведён набор тестов с реальными данными и алгоритмами QGIS для определения коэффициентов суб-CITF [уравнения (3) и (4)]. Как показано в Таблице 3, значимость всех моделей равна 0,0001, более 95% зависимостей могут быть объяснены всеми моделями (R² > 0,95), и значимость всех коэффициентов равна 0,0001. Таким образом, эти модели эффективны для оценки вычислительной интенсивности объекта.

Согласно коэффициентам в Таблице 3, вычислительная интенсивность объекта полилинии и полигона для буферного анализа может быть представлена уравнениями (11) и (12):

3.2 | Описание наборов данных и построение CIG для QGIS

Чтобы продемонстрировать доступность и эффективность предложенных нами методов PCCIL и TASD, в экспериментах используются два реальных векторных набора данных землепользования, как показано в Таблице 4. Набор данных A (Рисунок 11а) и набор данных B (Рисунок 11b) представляют соответственно полигональные и полилинейные географические объекты. Количество вершин объектов, распределённых в наборах данных, варьируется от 5 до 9 985. Некоторые объекты имеют правильную геометрию, включая правильные здания, правильные сельскохозяйственные угодья и т.д. Некоторые объекты неправильной формы, включая реки, озёра, неправильные сельскохозяйственные угодья и т.д. Согласно уравнениям (11) и (12), CIG могут быть созданы на основе наборов данных A и B. Когда гранулярность CIG составляет 32*32, CIG показана на Рисунках 11c и d. Различная высота и цвет используются для представления вычислительной интенсивности ячейки в CIG 32 × 32, и чем выше высота и темнее цвет, тем больше вычислительная интенсивность ячейки. Эффективность метода PCCIL для построения CIG будет продемонстрирована в разделе 3.4.

Рисунок 11 — CIG 32 x 32 для наборов данных A и B
(a) Набор данных A (полигон)
(b) Набор данных B (полилиния)
(c) CIG набора данных A (полигон)
(d) CIG набора данных B (полилиния)

3.3 | Анализ оптимальной гранулярности CIG для буферного анализа

Гранулярность CIG является решающим фактором, влияющим на балансировку нагрузки между задачами параллельного буферного анализа, и размер ячейки в CIG должен соответствовать пространственной вычислительной области, чтобы подобласти могли быть эффективно сформированы адаптивной пространственной декомпозицией первого этапа. Кроме того, гранулярность CIG также должна соответствовать количеству задач параллельного буферного анализа, и очевидно, что использование CIG 2 × 2 для генерации восьми подобластей, сформированных адаптивной пространственной декомпозицией первого этапа, не является точным. Как показано на Рисунке 12, восемь подобластей набора данных A сконструированы адаптивной пространственной декомпозицией первого этапа с соответствующими различными гранулярностями CIG. Очевидно, что диапазоны восьми подобластей при использовании CIG 2 × 2 и CIG 4 × 4 отличаются от остальных, и поэтому выбор оптимальной гранулярности CIG для оптимальной балансировки нагрузки между задачами параллельного буферного анализа является сложной и важной задачей.

Была проведена группа тестов с наборами данных A и B и различными соответствующими гранулярностями CIG в QGIS, чтобы получить оптимальную гранулярность CIG. Сначала набор данных A был распределён соответственно на два-восемь потоков для проведения буферного анализа с различными гранулярностями CIG, и стандартные отклонения времени вычислений потоков при определённом количестве задач (т.е. 2–8) с определённой гранулярностью CIG были вычислены как показатель балансировки нагрузки между потоками, чтобы получить оптимальную гранулярность CIG для буферного анализа набора данных A при определённом количестве задач (Рисунок 13). Затем, аналогично, была проведена группа экспериментов на наборе данных B, чтобы найти соответствующую оптимальную гранулярность CIG при определённом количестве задач (Рисунок 14). Как показано на Рисунках 13 и 14, для наборов данных A и B при использовании CIG 32 × 32 соответственно для двух-восьми потоков почти всегда достигается оптимальный баланс нагрузки. Следовательно, 32 × 32 является оптимальной гранулярностью для наборов данных A и B для проведения пространственной области параллельного буферного анализа. Затем предложенные методы были протестированы с использованием этой оптимальной гранулярности на наборах данных A и B (см. разделы 3.4 и 3.5).

Рисунок 12 — Использование различных гранулярностей CIG набора данных A для генерации восьми подобластей, сформированных FASD
(a) CIG 2*2 (b) CIG 4*4 (c) CIG 8*8 (d) CIG 16*16
(e) CIG 32*32 (f) CIG 64*64 (g) CIG 128*128 (h) CIG 256*256

Рисунок 13 — Стандартные отклонения времени вычислений потоков для набора данных A при использовании различных гранулярностей CIG

Рисунок 14 — Стандартные отклонения времени вычислений потоков для набора данных B при использовании различных гранулярностей CIG

При использовании оптимальной гранулярности вычислительные интенсивности подобластей были почти равны друг другу. В среде параллельных вычислений, если пространственная вычислительная область может быть разложена равномерно, можно получить максимальное ускорение. Из-за пространственной неоднородности векторных данных полностью равномерно разложить пространственную вычислительную область сложно. Однако мы можем использовать оптимальную гранулярность для представления пространственного распределения вычислительной интенсивности и достичь высокого ускорения насколько это возможно.

3.4 | Эксперименты и оценка производительности в QGIS

В разделе 3.3 мы получили оптимальную гранулярность сетки в группе экспериментов с алгоритмом буферного анализа QGIS. Используя эту гранулярность сетки, сначала TASD сравнивался с VD и HD, чтобы продемонстрировать производительность TASD. Кроме того, PCCIL и CCCIL использовались соответственно для генерации CIG, а затем параллельные задачи, декомпозированные одноэтапной адаптивной пространственной декомпозицией (OASD) и TASD, чтобы продемонстрировать, что стратегии PCCIL и TASD эффективны среди методов, основанных на вычислительной интенсивности.

Был выбран API QGIS для выполнения задачи параллельного буферного анализа с различным количеством потоков. Задачи параллельного буферного анализа генерируются подобластями, сформированными соответственно с помощью VD, HD и TASD. Методы VD и HD используют смежные подобласти для попеременного проведения пространственных запросов на пересечение и включение для получения непересекающихся задач параллельного буферного анализа (т.е. OASD). Эти методы легко программируются для параллельного буферного анализа, но они могут привести к сильному дисбалансу нагрузки. Поскольку 32 × 32 является оптимальной гранулярностью сетки CIG для наборов данных A и B, как упоминалось в разделе 3.3, CIG 32 × 32 используются для проведения следующей группы экспериментов, чтобы эффективно сравнить производительность TASD с VD и HD. Три различных результата декомпозиции на восемь подобластей для набора данных A с использованием VD, HD и TASD показаны на Рисунке 15. Очевидно, что результаты декомпозиции VD и HD неравномерны по вычислительной интенсивности, в то время как нагрузки подобластей, сгенерированных TASD, почти равны.

Была проведена последовательная программа буферного анализа с использованием наборов данных A и B соответственно, чтобы обеспечить эталон для оценки производительности параллельной программы. Время вычислений последовательного буферного анализа для набора данных A составило 23 076,335 мс, а для набора данных B — 50 272,347 мс. Был проведён набор экспериментов с использованием параллельной программы буферного анализа с различным количеством потоков (от двух до восьми). Как показано на Рисунке 16, при использовании нескольких потоков время вычислений для наборов данных A и B для буферного анализа значительно сокращается. Время вычислений уменьшается с увеличением количества потоков, и TASD показал наилучшую производительность во всех случаях. По сравнению со временем последовательного буферного анализа, время вычислений для восьми потоков на основе TASD достигло ускорения почти в реальном времени. На Рисунке 17 показано, что TASD достиг почти линейного ускорения для наборов данных A и B, и ускорение было значительно выше, чем у методов VD и HD, по мере увеличения количества потоков. Причиной почти линейного ускорения TASD является то, что учитывается пространственное распределение вычислительной интенсивности, и рабочая нагрузка равномерно распределяется по задачам параллельного буферного анализа. Для дальнейшей иллюстрации баланса производительности были рассчитаны стандартные отклонения времени вычислений всех потоков. Как показано на Рисунке 18, стандартные отклонения для наборов данных A и B на основе TASD значительно ниже, чем на основе VD и HD, что демонстрирует, что TASD обеспечил максимальную балансировку нагрузки между задачами параллельного буферного анализа. Для VD и HD количество векторных объектов, распределённых по подобластям, явно неравномерно. Это приводит к дисбалансу вычислительной интенсивности в подобластях и снижает ускорение. Следовательно, методы регулярной декомпозиции не подходят для декомпозиции пространственных вычислительных областей.

Упомянутые выше эксперименты эффективно оценили производительность TASD по сравнению с некоторыми методами регулярной декомпозиции (VD, HD), и следующая группа экспериментов была проведена для оценки производительности среди методов адаптивной пространственной декомпозиции, основанных на вычислительной интенсивности. PCCIL и CCCIL использовались соответственно для генерации CIG 32 × 32, а затем параллельные задачи были декомпозированы соответственно OASD и TASD. Были собраны времена вычислений четырёх методов для буферного анализа: CCCIL-OASD, PCCIL-OASD, CCCIL-TASD и PCCIL-TASD. В методах CCCIL-OASD и PCCIL-OASD подобласти получались с помощью OASD, а затем использовалась стратегия попеременного проведения пространственных запросов на пересечение и включение с помощью смежных подобластей для получения непересекающихся объектов. Комбинация PCCIL и TASD является нововведением данной статьи, и стандартные отклонения времени вычислений всех потоков для CCCIL-OASD, PCCIL-OASD, CCCIL-TASD и PCCIL-TASD были вычислены для демонстрации эффективности PCCIL и TASD. Механизм сканирования и декомпозиции вычислительной интенсивности OASD не учитывает векторные объекты, распределённые на границе двух подобластей. Поэтому он не может обеспечить максимальный баланс нагрузки между подобластями. Как показано на Рисунке 19, стандартные отклонения PCCIL-OASD и PCCIL-TASD соответственно ниже, чем у CCCIL-OASD и CCCIL-TASD, что указывает на то, что PCCIL может лучше представлять пространственное распределение вычислительной интенсивности для буферного анализа, чем CCCIL. И стандартные отклонения CCCIL-TASD и PCCIL-TASD оба значительно ниже, чем у CCCIL-OASD и PCCIL-OASD соответственно. Примечательно, что TASD может обеспечить лучший баланс, чем OASD, для декомпозиции задач параллельного буферного анализа. Другими словами, TASD является лучшим методом для балансировки нагрузки подзадач параллельного буферного анализа по сравнению с этими методами, основанными на вычислительной интенсивности.

Во всех экспериментав TASD показал наилучшую производительность, демонстрируя эффективную балансировку нагрузки TASD между различными потоками. Тем не менее, перед запуском потока необходимо было вычислить подобласти для соответствующих потоков. Время вычислений тестировалось с CIG 32 × 32, и результаты показали, что время вычислений довольно незначительно (обычно менее 10 мс), даже для больших пространственных векторных данных. В алгоритмах буферного анализа традиционных ГИС-платформ опция слияния (dissolving) результатов буферного анализа является опциональной. Если выбрана опция слияния всех объектов, некоторые буферные зоны сливаются в один объект, чтобы удалить любые перекрытия. В этом случае результаты, сгенерированные каждым потоком, необходимо объединить. Поскольку результаты буфера для подобластей уже объединены, следующие операции слияния проводятся только с этими объектами, пересекающими несколько подобластей. Сначала проводится пространственный запрос для получения всех объектов результатов, пересекающихся с границей между подобластями, а затем проводится второй запрос для получения всех целевых объектов, которые пересекаются с этими объектами. В конце проводятся операции слияния со всеми целевыми объектами, и соответствующие результаты показывают, что время слияния также довольно незначительно (обычно менее 10 мс). Затем результаты необходимо объединить, и была проведена группа тестов. Результаты также показывают, что время довольно незначительно (обычно менее 3 мс). Следовательно, высокая производительность TASD может быть обеспечена в нашем параллельном фреймворке буферного анализа.

Рисунок 15 — Три типа декомпозиции для набора данных A: (a) VD (b) HD (c) TASD

Рисунок 16 — Время вычислений для наборов данных A и B с тремя параллельными методами и от двух до восьми потоков

Рисунок 17 — Ускорение для наборов данных A и Б с тремя параллельными методами и от двух до восьми потоков

Рисунок 18 — Стандартные отклонения для наборов данных A и B с тремя параллельными методами и от двух до восьми потоков

Рисунок 19 — Стандартные отклонения для наборов данных A и B при использовании четырёх методов и от двух до восьми потоков

3.5 | Эксперименты и оценка производительности в ArcGIS и MapGIS

Вышеупомянутые эксперименты доказали отличную производительность наших методов на платформе QGIS. Следующая группа экспериментов была проведена на платформах ArcGIS и MapGIS, чтобы доказать универсальность наших методов. В этих экспериментах также использовались наборы данных A и B, и CIG 32 × 32 применялись для декомпозиции задач параллельного буферного анализа. Время последовательного буферного анализа набора данных A в ArcGIS составило 360 159,3802 мс, а набора данных B — 383 396,9572 мс; набора данных A в MapGIS — 17 946,66708 мс, а набора данных B в MapGIS — 55 051,4359 мс. Соответствующие последовательные времена вычислений для наборов данных A и B различались между ArcGIS и MapGIS, потому что алгоритмы буферного анализа, используемые в ArcGIS и MapGIS, разные. Однако, если хорошая производительность наших методов может быть продемонстрирована как в ArcGIS, так и в MapGIS, это может полностью доказать универсальность и эффективность наших методов.

Как показано в Таблицах 5 и 6, были получены времена вычислений для наборов данных A и B с двумя-восемью потоками в ArcGIS. Несмотря на то, что задачи буферного анализа выполнялись с использованием различного количества потоков, параллельные времена вычислений для наборов данных A и B были сбалансированы. Были рассчитаны соответствующие стандартные отклонения потоков для наборов данных A и B, и результаты демонстрируют производительность балансировки нагрузки между параллельными задачами. В Таблицах 7 и 8 были проведены те же эксперименты в MapGIS. Результаты также показывают отличную производительность балансировки нагрузки задач параллельного буферного анализа на основе наших методов. Как показано на Рисунке 20, наборы данных A и B с различным количеством потоков от двух до восьми в ArcGIS и MapGIS все достигли почти линейного ускорения, что полностью демонстрирует выдающуюся производительность наших методов.

Рисунок 20 — Ускорение для наборов данных A и Б в ArcGIS и MapGIS с двумя-восемью потоками

Приведённые выше экспериментальные результаты демонстрируют, что предложенный в данном исследовании TASD является универсальным и эффективным для этих трёх традиционных ГИС-платформ. Почти линейное ускорение может быть достигнуто как для разного количества подобластей, что означает, что новый подход может быть использован на разном количестве ядер параллельных вычислений.

4 | ВЫВОДЫ

Буферный анализ является одной из основных функций пространственного анализа ГИС. С увеличением объёмов пространственных данных традиционные алгоритмы векторного буферного анализа не могут удовлетворить требованиям быстрой обработки данных. В данном исследовании предложен универсальный метод параллельного планирования, использующий формат данных и алгоритмы векторного буферного анализа традиционных ГИС-платформ для буферного анализа, что позволяет достичь хорошей производительности параллельного векторного буферного анализа на этих традиционных ГИС-платформах.

Серия экспериментов была проведена в параллельном фреймворке буферного анализа для трёх типичных традиционных ГИС-платформ с использованием группы реальных наборов данных полилиний и полигонов. Сначала программа параллельного буферного анализа на основе TASD была проведена на платформе QGIS с двумя-восемью потоками и сравнена с методами, основанными на регулярной декомпозиции. TASD показал наилучшую производительность во всех экспериментах. Затем, чтобы дополнительно исследовать универсальность предложенных методов, эксперименты также были проведены на платформах ArcGIS и MapGIS, и высокая производительность балансировки нагрузки также была продемонстрирована.

В заключение, предложенные в данной статье PCCIL и TASD способны обеспечить балансировку нагрузки между задачами параллельного буферного анализа на этих трёх типичных традиционных ГИС-платформах и достичь максимальной параллельной эффективности. Очень важно и полезно, что соответствующий формат данных и алгоритмы буферного анализ традиционных ГИС-платформ не требуют конвертации и переразработки. Предложенный нами универсальный подход к параллельному планированию для буферного анализа векторных данных традиционных ГИС-платформ является эффективным и демонстрирует отличную производительность для любого типа алгоритма буферного анализа на любой ГИС-платформе. Будущая работа будет сосредоточена на разработке новых параллельных алгоритмов анализа наложения и отсечения, чтобы в полной мере использовать такой подход к декомпозиции и дополнительно повысить производительность.

БЛАГОДАРНОСТИ

Данная работа была поддержана Национальным фондом естественных наук Китая (гранты № 41971356 и 41701446).

ССЫЛКИ